
//力扣31. 下一个排列
class Solution {
    public void nextPermutation(int[] nums) {
        int k = nums.length - 2;
        while (k >= 0 && nums[k] >= nums[k + 1]) {
            k--;
        }

        if (k == -1) {
            // 整个数组是降序排列，直接翻转整个数组
            reverse(nums, 0, nums.length - 1);
            return;
        }

        // 找到第一个比nums[k]大的数
        int min = nums.length - 1;
        while (nums[min] <= nums[k]) {
            min--;
        }

        // 交换nums[k]和nums[min]
        swap(nums, k, min);

        // 翻转k+1到末尾的部分
        reverse(nums, k + 1, nums.length - 1);
    }

    private void reverse(int[] nums, int start, int end) {
        while (start < end) {
            swap(nums, start, end);
            start++;
            end--;
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

//力扣75. 颜色分类
class Solution1 {
    public void sortColors(int[] nums) {
        int zero = 0;
        int two = 0;
        int one = 0;
        for(int i=0;i<nums.length;i++){
            if(nums[i]==0){
                zero++;
            }else if(nums[i]==1){
                one++;
            }else{
                two++;
            }
        }
        int k = 0;
        while(zero--!=0){
            nums[k++]=0;
        }
        while(one--!=0){
            nums[k++]=1;
        }
        while(two--!=0){
            nums[k++]=2;
        }
    }
}

//力扣287. 寻找重复数
class Solution2 {
    public int findDuplicate(int[] nums) {
        int slow = nums[0];
        int fast = nums[0];

        // 将数组视为一个链表，其中 nums[i] 表示从节点 i 指向节点 nums[i] 的边。
        // 第一阶段：找到快慢指针相遇点
        do {
            //slow 每次走 1 步（slow = nums[slow]）。
            //fast 每次走 2 步（fast = nums[nums[fast]]）。
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);

        // 第二阶段：找到环的入口（即重复数字）
        slow = nums[0];
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }

        return slow;
    }
}